/**
 * 删除元素为x的子树，并释放空间
 * 删除元素为x的子树，要删除他的左子树和右子树，就可以释放x根节点
 * 思想是：用层次遍历找到某个节点的父节点，然后删除
 */
#include "BiTree.h"
void del(BiTree *root)
{ // 递归删除
    if (root)
    {
        del(root->left);
        del(root->right);
        delete root;
    }
}
#include <queue>
using namespace std;
void search(BiTree *bt, int x)
{
    BiTree *p;
    queue<BiTree *> q;
    if (bt)
    {
        if (bt->val == x)
        { // 找到了x
            del(bt);
            return;
        }
        q.push(bt);
        while (!q.empty())
        {
            p = q.front();
            q.pop();

            if (p->left)
            {
                if (p->left->val == x)
                {
                    del(p->left);
                    p->left = nullptr;
                }
                else
                {
                    q.push(p->left);
                }
            }
            if (p->right)
            {
                if (p->right->val == x)
                {
                    del(p->right);
                    p->right = nullptr;
                }
                else
                {
                    q.push(p->right);
                }
            }
        }
    }
}